package top.fengleifeng.question;

import top.fengleifeng.util.Constants;

import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

/**
 * @program: leetcode-test
 * @description:
 * @author: fengleifeng
 * @create: 2020-09-24 20:15
 **/
public class Num501二叉搜索树中的众数 {
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int[] findMode(TreeNode root) {
            if (root == null) {
                return new int[0];
            }
            int max = 0;
            HashMap<Integer, Integer> map = new HashMap<>();
            List<Integer> list = new LinkedList<>();
            dfs(root, map);
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            while (iterator.hasNext()) {
                Map.Entry<Integer, Integer> entyr = iterator.next();
                Integer key = entyr.getKey();
                Integer value = entyr.getValue();
                if (value > max) {
                    max = value;
                    list.clear();
                    list.add(key);
                } else if (value == max) {
                    list.add(key);
                }
            }
            int[] reuslt = new int[list.size()];
            for (int j = 0; j < list.size(); j++) {
                reuslt[j] = list.get(j);
            }
            return reuslt;
        }

        private void dfs(TreeNode now, HashMap<Integer, Integer> map) {
            if (now == null) {
                return;
            }
            if (map.containsKey(now.val)) {
                map.put(now.val, map.get(now.val) + 1);
            } else {
                map.put(now.val, 1);
            }
            dfs(now.left, map);
            dfs(now.right, map);
        }
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(1);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(2);
        one.right = right;
        int[] mode = new Num501二叉搜索树中的众数().new Solution().findMode(one);
        Constants.printArr(mode);
    }
}
